//@原文链接：https://blog.csdn.net/ITSOK_123/article/details/124497889
//优先队列解题——大顶堆（O(NlogN)）,O(N)
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        int len = nums.size();
        //先对数组进行排序，方便统计频率
        sort(nums.begin(),nums.end());
        // 初始化优先队列用来保存频率-元素值对
        priority_queue<pair<int,int>> que;
        for(int i=0;i<len;i++){
            int p=1;
            //遇到相等元素值，频率增加，指针右移
            while(i+1<len && nums[i]==nums[i+1]){
                p++;
                i++;
            }
            //频率元素对插入队列
            que.emplace(p,nums[i]);
        }
        vector<int> res;
        //输出前k个高频元素
        while(k--){
            res.push_back(que.top().second);
            que.pop();
        }
        return res;
    }
};
//小顶堆（O(Nlogk),O(N)）
class Solution {
public:
    //定义比较顺序
    struct cmp{
        public:
        bool operator()(const pair<int,int> &p1,const pair<int,int> &p2){
             return p1.second>p2.second;
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // 统计元素值和频率映射
        unordered_map<int,int> occurences;
        for(auto c:nums){
            occurences[c]++;
        }
        // 小顶堆的定义
        priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> pri_que;
        //根据map内元素键值对进行小顶堆的数据保存
        for(unordered_map<int,int>::iterator iter=occurences.begin();iter!=occurences.end();++iter){
            pri_que.push(*iter);
            if(pri_que.size()>k){
                pri_que.pop();
            }
        }
        vector<int> res;
        //保存k个元素
        while(k--){
            res.push_back(pri_que.top().first);
            pri_que.pop();
        }
        return res;
    }
};
//基于快排划分数组（O(N)）
class Solution {
public:
    void quick_sort(vector<pair<int,int>> &vp,int start,int end,int k,vector<int>& res){
        //随机确定基准元素
        int picked = rand()%(end-start+1)+start;
        swap(vp[start],vp[picked]);

        int pivot = vp[start].second;
        //同向双指针快排partition函数
        int index = start;
        for(int i=start+1;i<=end;i++){
            if(vp[i].second>=pivot){
                index++;
                swap(vp[i],vp[index]);
            }
        }
        swap(vp[start],vp[index]);
        //如果基准元素及其左边的元素个数大于k个，
        //说明找多了，则在左边缩小范围继续查找
        if(k<index-start+1){
            quick_sort(vp,start,index-1,k,res);
        }else{
            //否则就是找少了，则先将找到的最大个index-start+1个元素进行保存
            // 再找剩下的k-(index-start+1)个元素
            for(int i=start;i<=index;i++){
                res.push_back(vp[i].first);
            }
            if(k>index-start+1){
                quick_sort(vp,index+1,end,k-(index-start+1),res);
            }
        }
    }
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // 保存元素频率映射
        unordered_map<int,int> m;
        for (auto& v : nums) {
            m[v]++;
        }
        //map不方便进行排序，采用vector辅助操作
        vector<pair<int,int>> pm;
        for(auto &pa:m){
            pm.push_back(pa);
        }
        vector<int> res;
        quick_sort(pm,0,pm.size()-1,k,res);
        return res;
    }
};
